package Other;

import java.util.Arrays;

//494. 目标和
public class FindTargetSumWays {

    public static void main(String[] args) {
     Solution2999 s=new Solution2999();
     int[] nums={1,1,1,1,1,1};
     s.findTargetSumWays(nums, 3);
    }
    
}


//搜索+回溯
// class Solution {
    // int ans =0;
    // int[] nums;
    // int S;
    // public int findTargetSumWays(int[] nums, int S) {
        // this.nums=nums;
        // this.S=S;
        // search(0,0);
        // return ans;
    // // }

    // private void search(int sum,int start){
        // if(start==nums.length-1){
            // if(sum+nums[start]==S) ans++;
            // if(sum-nums[start]==S) ans++;
            // return;
        // }
        // search(sum+nums[start], start+1);
        // search(sum-nums[start], start+1);
    // }
// }

//dp
// class Solution2999 {
//     public int findTargetSumWays(int[] nums, int S) {
//         int[][] dp = new int[nums.length][2001];
//         dp[0][nums[0] + 1000] = 1;
//         dp[0][-nums[0] + 1000] += 1;
//         for (int i = 1; i < nums.length; i++) {
//             for (int sum = -1000; sum <= 1000; sum++) {
//                 if (dp[i - 1][sum + 1000] > 0) {
//                     dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000];
//                     dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000];
//                 }
//             }
//         }
//         return S > 1000 ? 0 : dp[nums.length - 1][S + 1000];
//     }
// }
